package 数学作业.homework3.test1;

import java.util.Random;

public class 插入排序 {
    public static void main(String[] args) {
        Random ran = new Random();
        int[] arr = new int[100];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = ran.nextInt(101);
        }
        insertSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {//注意从第二个元素开始
            int key = arr[i];
            int end = i - 1;//设置当前坐标
            //如果当前坐标小于key，那么当前坐标前移
            while (end >= 0 && arr[end] > key) {
                //注意上面的arr[end] > key不能加等号，不然会不稳定的
                if (arr[end] > key) {
                    arr[end + 1] = arr[end];
                    end--;
                }
            }
            //最后这里的+1，是因为不论是否匹配成功end都要--
            arr[end + 1] = key;
        }
    }
}
